package leetcode.editor.cn.q1_300.q200;
//给定一个字符串 s，你可以通过在字符串前面添加字符将其转换为回文串。找到并返回可以用这种方式转换的最短回文串。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "aacecaaa"
//输出："aaacecaaa"
// 
//
// 示例 2： 
//
// 
//输入：s = "abcd"
//输出："dcbabcd"
// 
//
// 
//
// 提示： 
//
// 
// 0 <= s.length <= 5 * 10⁴ 
// s 仅由小写英文字母组成 
//

import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 思路，让数组逐个添加 last元素，知道变成回文串
 *
 * 怎么说呢，自我感觉是个挺不错的思路，但是只超过 5%
 *
 * 官网推荐使用 kmp 或者 manacher 先找到最小回文串，然后直接添加字符串成回文串返回
 */
public class Q214_ShortestPalindrome {
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String shortestPalindrome(String s) {
            if (s == null || s.length() == 0) return "";

            int n = s.length();
            char[] arr = s.toCharArray();
            List<Character> chars = IntStream.range(0, n).mapToObj(i -> arr[i]).collect(Collectors.toList());
            int mov = 0;
            while (mov != n) {
                if (isPalind(n, arr, chars, mov)) {
                    break;
                }
                mov++;
            }

            StringBuilder res = new StringBuilder();
            for (Character c : chars) {
                res.append(c);
            }
            return res.toString();
        }

        private boolean isPalind(int n, char[] arr, List<Character> chars, int mov) {
            int i = mov;
            int m = chars.size();
            while (i < m / 2) {
                if (!chars.get(i).equals(chars.get(m - i - 1))) {
                    chars.add(mov, arr[n - mov - 1]);
                    return false;
                }
                i++;
            }
            return true;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)


    public static void main(String[] args) {
        Solution solution = new Q214_ShortestPalindrome().new Solution();
        // TO TEST
        System.out.println(solution.shortestPalindrome("aaacecaaa"));
        System.out.println(solution.shortestPalindrome("aacecaaa"));
        System.out.println(solution.shortestPalindrome("abcd"));
    }
}